⟸ Go Back ⟸

Exercise 3 (Homework 2).

(regular languages, concatenation, minimization of DFAs)

Concatenation of regular languages is regular

1. Construct the minimum DFA for the language L_1\cdot L_2, where

   1. L_1=\{xaya\mid x,y\in\{a,b\}^*\} and L_2=\{bxby\mid x,y\in\{a,b\}^*\}.
   2. L_1=\{xaay\mid x,y\in\{a,b\}^*\} and L_2=\{bxb\mid x\in\{a,b\}^*\}.
   3. L_1=\{xaya\mid x,y\in\{a,b\}^*\} and L_2=\{bxb\mid x\in\{a,b\}^*\}.

   Find the minimum DFAs recognizing L_1 and L_2. From those DFAs, construct a \lambda-NFA A recognizing the language L_1\cdot L_2. Now, using the power-set construction, make A deterministic and minimize the DFA obtained.

2. Given two DFAs A and B as input, what is the cost of constructing a DFA for L(A)\cdot L(B)?